#include<stdio.h>
#include<string.h>
#include<math.h>
#define true 1
#define false 0

// char pat[256];      // the pattern  // needed only for Las Vegas
long patHash = 0; // pattern hash value
long Q = 0; // a large prime, small enough to avoid long overflow
int R = 256; // radix
long RM = 0;
// R^(M-1) % Q
typedef int bool;
char pattern[4096];
char text[4096];

void patternHash(char *pat, int patternLength);
long hash(char* key, int M);
bool check(char* txt, int i, int M);
int search(char* txt, int N , int patternLength);
long longRandomPrime();

void patternHash(char *pat, int patternLength) {
    int i = 0;
    printf(" in code patternHash text is %s and len is%d\n", pat, patternLength);
    Q = longRandomPrime();
    RM = 1;
    for (i = 1; i <= patternLength - 1; i++) {
        RM = (R * RM) % Q;
    }
    printf(" value of Q is%ld\n", Q);
    printf(" value of Rm is%ld\n", RM);
    printf(" value of R is%d\n", R);
    patHash = hash(pat, patternLength);
}

// Compute hash for key[0..M-1].

long hash(char* key, int len) {
    int j = 0;
    long h = 0;
    for (j = 0; j < len; j++) {
        h = (R * h + key[j]) % Q;
    }
    printf(" value of hash is %ld\n", h);
    return h;
}


bool check(char* txt, int k, int M) {
    int j = 0;
    for (j = 0; j < M; j++) {
        if (pattern[j] != txt[k + j]) {
            return false;
        }

    }
    return true;
}


int search(char *txt, int textLength, int patternLength) {
   
    int i,val=0;
    printf("in method search text is %s and N is %d\n", txt, textLength);
    //if (textLength < patternLength) return textLength;
    long txtHash = hash(txt, patternLength);
    // check for match at offset 0
    bool returnCheck;

    returnCheck = check(txt, 0, patternLength);
    if ((patHash == txtHash) && returnCheck){
        val++;
    }
       

    // check for hash match; if hash match, check for exact match
    printf(" value of Q is%ld\n", Q);
    printf(" value of Rm is%ld\n", RM);
    printf(" value of R is%d\n", R);
    
    for (i = patternLength; i < textLength; i++) {
        printf(" value of i is%d\n", i);
        // Remove leading digit, add trailing digit, check for match.
        txtHash = (txtHash + Q - RM * txt[i - patternLength] % Q) % Q;
        txtHash = (txtHash * R + txt[i]) % Q;

        // match
        int offset = i - patternLength + 1;
        returnCheck = check(txt, offset,patternLength);
        printf(" value of offset is %d, return from check is%d", offset, returnCheck);
        if ((patHash == txtHash) && check(txt, offset,patternLength)){
            val++;
        }
    }
    if(val>0){
        return val ;
    }
    // no match
    return textLength;
}


// a random 31-bit prime

long longRandomPrime() {
    srand((2^31) - 1);
    long prime = rand();
     //printf("in method longRandomPrime value of random prime is %ld \n",prime);
    return prime;
}

// test client

int main(int argc, char** argv) {
    printf(" enter a string\n");
    fgets(text, sizeof (text), stdin);
    printf(" enter a pattern\n");
    fgets(pattern, sizeof (pattern), stdin);
    int n = strlen(text);
    int m = strlen(pattern);
    printf(" text is %s %d  pattrn is %s %d \n", text, n-1, pattern, m-1);
    patternHash(pattern, m-1);
    int offset=0;
    if(n>m){
    offset = search(text, n-1,m-1);
    }
    printf(" the number of times the pattern is occuring is%d\n", offset);
    return 1;

}
